---
title: "搭积木"
created: 2025-11-28
tags:
  - 算法
---

# 搭积木

## 题目 [搭积木](https://lanqiao.cn/paper/3851/problem/225/)

![[image-8508236b.png]]

## 思路分析

![[image-05a502d2.png]]

题目意思看懂了 但是不怎么好下手

数据范围挺小的 100

暴搜把所有情况弄出来判断合法与否估计能拿些分（类似于八皇后问题的按点枚举的写法）

有点巧妙

- **mem[num][left][right]** 数组用来存储从第 **num** 层积木放置，从位置 **left** 到 **right** 的所有可能的方案数。这样可以避免重复计算相同状态，实现记忆化。
- **arr[i][j]** 存储每一层积木放置的喜好。

**dfs(num, left, right)**:

- 当 **num == 0** 时，表示没有更多层可以放置积木，返回 0。
- 对于任意 **num != 0**，遍历当前层 **num** 从位置 **left** 到 **right**：
  - 如果位置 **i** 是 '.'（可以放置积木），则从这个位置开始尝试放置积木，直到遇到 'X' 或到达 **right**。
  - 对于每个有效的连续段 **[i, j]**，计算在下一层 **num-1** 上同样的段 **[i, j]** 可能的放置方案数，并将其加到总和中。
- 结果中包含一个加一的操作，这表示在当前层 **[left, right]** 区间内至少放置一个积木的方案数。

## 代码实现

```cpp
#include <iostream>

#include <cstring>

using namespace std;

typedef long long ll;

#define N 105

const ll mor=7+1e9;

char arr[N][N];

ll mem[N][N][N];

int n, m;

ll dfs(int num, int left, int right) {

    if (mem[num][left][right]!=-1) return mem[num][left][right];

    if (num == 0) mem[num][left][right] = 0;

    else if (num != 0) {

        ll sum = 0;

        for (int i = left; i <= right; i++) {

            if (arr[num][i] == '.') {

                for (int j = i; j <= right; j++) {

                    if (arr[num][j] != 'X') {

                        sum += dfs(num - 1, i, j) + 1;

                    }

                    else break;

                }

            }

        }

        mem[num][left][right] = sum%mor;

    }

    return mem[num][left][right];

}

int main()

{

    // 请在此输入您的代码

    memset(mem, -1, sizeof mem);

    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {

        scanf("%s", &arr[i][1]);

    }

    cout << (dfs(n, 1, m) + 1)%mor;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[调手表|调手表]] 🏠 [[00-冲刺国赛]] ➡️ [[矩阵求和|矩阵求和]]